package LinkedList;

public class _92_ReverseLinkedListII {
    //总结：省去消耗时间的判断，使用多个指针（开始反转的上一个指针prev，反转头部指针start，需反转的指针then，start.next=then.next来连接反转后的后半部分链表，prev连接前半部分链表）
    //may be right,memory limit exceeded
    public ListNode reverseBetween1(ListNode head, int m, int n) {
        if(m==n){
            return head;
        }
        ListNode pbegin = null,pend = null,begin = null,end = null,p = head;
        int count = 0;
        while(p!=null){
            count++;
            if(count+1 == m){
                pbegin = p;
            }
            if(count-1 ==n){
                pend = p;
            }
            if (count == m) {
                begin = p;
            }
            if (count == n) {
                end = p;
            }
            p = p.next;
        }
        ListNode[] interval = reverse(begin,end);
        if(pbegin!=null){
            pbegin.next = interval[0];
        }else{
            head =  interval[0];
        }
        System.out.println(interval[1].val);
        if(pend!=null){
            interval[1].next = pend;
        }
            return head;
    }

    public ListNode[] reverse(ListNode begin,ListNode end){
        ListNode rend = begin,rbegin = end,p = begin;
        ListNode prev = null;
        while(p!=null){
            ListNode temp = p.next;
            p.next = prev;
            prev = p;
            p  = temp;
        }
        return new ListNode[]{rbegin,rend};
    }

    //memory limit exceeded
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if(m==n){
            return head;
        }
        ListNode prev = null;
        ListNode p  =head;
        ListNode tempBegin = head;
        if(m==1){
            int count = 0;
            while(p!=null){
                ListNode temp = p.next;
                count++;
                if(count<=n){
                    p.next = prev;
                    prev = p;
                }
                if(count==n && p.next!=null){
                    tempBegin.next = p.next;
                    return p;
                }else if(count==n && p.next==null){
                    return p;
                }
                p  = temp;
            }
        }else{
            ListNode pbegin = null;
            int count = 0;
            while(p!=null){
                ListNode temp = p.next;
                count++;
                if (count + 1 == m) {
                    pbegin = p;
                }
                if(count<=n){
                    p.next = prev;
                    prev = p;
                }
                if(count==n && p.next!=null){
                    tempBegin.next = p.next;
                    pbegin.next = p;
                    return head;
                }else if(count==n && p.next==null){
                    return head;
                }
                p  = temp;
            }
        }
        return head;
    }

    //参考
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
        dummy.next = head;
        ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
        for(int i = 0; i<m-1; i++) pre = pre.next;

        ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
        ListNode then = start.next; // a pointer to a node that will be reversed

        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5

        for(int i=0; i<n-m; i++)
        {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }

        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)

        return dummy.next;

    }
}
